# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=30
    
    PROBLEM
    
    Surprisingly there are only three numbers that can be written as the
    sum of fourth powers of their digits:

    1634 = 14 + 64 + 34 + 44
    8208 = 84 + 24 + 04 + 84
    9474 = 94 + 44 + 74 + 44

    As 1 = 14 is not a sum it is not included.

    The sum of these numbers is 1634 + 8208 + 9474 = 19316.

    Find the sum of all the numbers that can be written as the sum of fifth
    powers of their digits.

    
    NOTES

    
    REFERENCES
    
    
    PERFORMANCE
    time <function solution at 0x7f3df8371ed8>: 2.138727 s
    
"""
#
# Import
#
import time
import random


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    f = "value %s != expected %s"
    f = message != '' and f + " (%s)" or f + "%s"
    assert value == expected, f % (value, expected, message)


#
# Test Case / Solution
#
@timeit    
def test_case():
    max_digit_4 = get_max_power_digit(4)
    assert max_digit_4 < 100000
    
    power_digit_sums = get_sum_of_power_digit_sums(4)
    assert_match(power_digit_sums, 19316)
    
    print "test case passed!"

@timeit
def solution():
    return get_sum_of_power_digit_sums(5)

#
# Solution Code
#
def get_sum_of_power_digit_sums(power):
    max_power_digit = get_max_power_digit(power)
    power_digit_sums = []
    
    for n in range(10, max_power_digit):
        power_digit_sum = get_power_digit_sum(n, power)
        if power_digit_sum == n:
            power_digit_sums.append(n)
    
    #print power_digit_sums
    return sum(power_digit_sums)

def get_max_power_digit(power):
    max_power_sum = 0
    n = 0
    
    while n <= len(str(max_power_sum)):
        n += 1
        max_power_sum = sum([9**power] * n)
        #print n, max_power_sum, len(str(max_power_sum))
        
    return min(int('9'*(n-1)), max_power_sum)

def get_power_digit_sum(number, power):
    digits = map(int, list(str(number)))
    return sum([n**power for n in digits])
        


#
# Additional Tests
#


#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    